package demo.practice.leetcode_trie;

import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {
    boolean isend = false;
    Map<Character, Solution> children = new HashMap<>();

    //https://leetcode-cn.com/leetbook/read/trie/x0cga2/ 单词替换
    public Solution() {

    }

    public static void main(String[] args) {
        Solution s= new Solution();
        String s1 = s.replaceWords(Arrays.asList("cat", "bat", "rat"), "the cattle was rattled by the battery");
        System.out.printf(s1);

    }

    public void insert(String words) {
        Solution current = this;
        for (int i = 0; i < words.length(); i++) {
            char c = words.charAt(i);
            if (current.children.get(c) == null) {
                current.children.put(c, new Solution());
            }
            current = current.children.get(c);
        }
        current.isend = true;
    }

    public String replaceWords(List<String> dictionary, String sentence) {
        for (String d : dictionary) {
            insert(d);
        }

        StringBuilder sb = new StringBuilder();

        String[] sens = sentence.split(" ");
        for (int i = 0; i < sens.length; i++) {
            if (i != sens.length - 1) {
                sb.append(find(sens[i]) + " ");
            } else
                sb.append(find(sens[i]));
        }

        return sb.toString();
    }

    private String find(String words) {
        Solution current = this;
        for (int i = 0; i < words.length(); i++) {
            char c = words.charAt(i);
            if (current.children.get(c) == null) {
                return words;
            } else {
                if (current.children.get(c).isend)
                    return words.substring(0, i+1);
                else
                    current = current.children.get(c);
            }
        }
        return words;
    }

}
